1. Field of the Invention
The present invention relates to an encoder using Huffman codes. More particularly, the present invention relates to an encoder capable of selecting the optimal Huffman codebook from among a plurality of Huffman codebooks so as to encode digital data by using the optimally selected Huffman codebook.
2. Description of the Related Art
In recent years, efficient audio signal compression methods encode spectral data of quantized audio signals by using a Huffman encoding scheme. A conventional data compression method, for example, a data compression method disclosed in the MPEG2-AAC standard will now be described (see ISO/IEC 13818-7).
First, an input PCM (Pulse Code Modulation) signal is converted through an MDCT (Modified Discrete Cosine Transform) operation into 1024 elements of frequency spectral data. This process is described in detail in xe2x80x9cISO/IEC 13818-7 ANNEX B 2.3 FilterBank and block switchingxe2x80x9d and will not be discussed below. xe2x80x9cISO/IEC 13818-7 ANNEX B 2.3 FilterBank and block switching is incorporated by reference in its entirety.
Then, the 1024 elements of frequency spectral data are quantized (converted into integers) by using a non-linear quantization method. This process is described in detail in xe2x80x9cISO/IEC 13818-7 ANNEX B 2.7 Quantizingxe2x80x9d and will not be discussed below. xe2x80x9cISO/IEC 13818-7 ANNEX B 2.7 Quantizingxe2x80x9d is incorporated by reference in its entirety.
Next, the 1024 elements of quantized frequency spectral data are grouped into a number of scale factor bands (in this specification, a scale factor band (SFB) may also be referred to as a xe2x80x9cgroup of dataxe2x80x9d). Using a sampling frequency of 48 kHz, for example, the 1024 elements of quantized frequency spectral data would be grouped into 49 SFBs. Referring now to FIG. 14, the grouping of frequency spectral data is performed as shown in a table 450. For example, the frequency spectral data is grouped into SFBs so that SFB0 includes four elements 0-3 of the frequency spectral data (as shown in row 451), SFB1 includes four elements 4-7 of the frequency spectral data (as shown in row 452), and SFB2 includes four elements 8-11 of the frequency spectral data.(as shown in row 453) (see xe2x80x9cISO/IEC 13818-7 3.8 Tablesxe2x80x9d).
Referring to FIG. 15, a table 500 illustrating frequency spectral data which has been quantized and grouped into a number of SFBs (SFB0 to SFB(Gxe2x88x921)) in a process as described above is shown. In FIG. 15, left column 501 designated xe2x80x9cSFBxe2x80x9d shows a number of SFBs (SFB0 to SFB(Gxe2x88x921)), center column 502 designated xe2x80x9cspectrumxe2x80x9d shows frequency spectral data numbers, and right column 503 designated xe2x80x9cvaluexe2x80x9d shows the absolute value of each frequency spectral data.
Then, the quantized and grouped frequency spectral data is Huffman-encoded for each SFB. The Huffman encoding operation is performed based on one Huffman codebook which is selected for each SFB from among a plurality of Huffman codebooks. According to the MPEG2-AAC standard, a Huffman codebook is selected from among eleven Huffman codebooks (Huffman codebooks 1-11). In the following description, however, only four Huffman codebooks (Huffman codebooks 3-6) are used for the sake of simplicity.
FIGS. 16 to 19 illustrate Huffman codebooks 3-6, respectively. In the Huffman codebooks 3-6 illustrated in FIGS. 16 to 19, respectively, the leftmost column designated xe2x80x9cindexxe2x80x9d shows the index number of each data to be encoded, the second column designated xe2x80x9clengthxe2x80x9d shows the code length of each encoded data, and the third column designated xe2x80x9ccodeword (hexadecimal)xe2x80x9d shows a hexadecimal representation of each encoded data (codeword). The Huffman codebooks 3-6 illustrated in FIGS. 16 to 19 each contain the code length of each encoded data (length) and a hexadecimal representation of each encoded data (codeword) for index numbers 0-80.
In SFB0 shown in FIG. 15, the largest absolute spectral data value is 4. According to the MPEG2-AAC standard, Huffman codebooks that can be selected for an input signal are limited by the largest absolute value of the input signal. This limitation is determined by LAV (largest absolute value) as shown in FIG. 20. LAV of a Huffman codebook denotes the largest absolute value of input data that can be encoded by using a particular Huffman codebook. According to the table shown in FIG. 20, when the largest absolute spectral data value in SFB0 is 4, Huffman codebooks 5 and 6 are the candidate Huffman codebooks. The code length which would result when encoding data with the candidate Huffman codebook 5 is compared with the code length which would result when encoding data with the candidate Huffman codebook 6. The candidate Huffman codebook that gives the smaller code length is selected. In this example, where the Huffman codebooks 5 and 6 are candidates, the code length which would result when Huffman-encoding data with the candidate Huffman codebooks is calculated as follows:
First, two index values xe2x80x9cindex0xe2x80x9d and xe2x80x9cindex1xe2x80x9d are calculated from Expressions (1) and (2) below:
index0=(D0+LAV)*(2*LAV+1)+(D1+LAV)xe2x80x83xe2x80x83(1)
index1=(D2+LAV)*(2*LAV+1)+(D3+LAV)xe2x80x83xe2x80x83(2)
where D0, D1, D2 and D3 respectively denote the four spectral data elements (values) of SFB0. The calculated values of xe2x80x9cindex0xe2x80x9d and xe2x80x9cindex1xe2x80x9d are used as the index values. The code length xe2x80x9clengthxe2x80x9d for the candidate Huffman codebooks 5 and 6 is obtained based on the index values.
Referring to FIG. 15, substituting the following values into Expressions (1) and (2), D0=4, D1=-2, D2=0, D3=3 and LAV=4, result in index0=74 and index1=43. Referring to the Huffman codebook 5 shown in FIG. 18, a length=12 for index0=74 and a length=8 for index1=43 can be determined, indicating that the code length would be 20 (12+8) bits when Huffman-encoding data with the Huffman codebook 5. Referring to the Huffman codebook 6 shown in FIG. 19, a length=9 for index0=74 and a length=7 for index1=43 can be determined, indicating that the code length would be 16 (9+7) bits when Huffman-encoding data with the Huffman codebook 6. Therefore, it is more advantageous to select the candidate Huffman codebook 6 for encoding each spectral data included in SFB0. Thus, the Huffman codebook 6 is selected.
Similarly, for SFB1, the code length would be 18 bits when encoding data with the Huffman codebook 5, and 13 bits when encoding data with the Huffman codebook 6. Therefore, it is more advantageous to also select the Huffman codebook 6 for encoding each spectral data included in SFB1. Thus, the Huffman codebook 6 is selected.
For SFB2 shown in FIG. 15, whose largest absolute spectral data value is 1, the Huffman codebooks 3-6 are the candidate Huffman codebooks. For the Huffman codebooks 5 and 6, the code length of Huffman-encoded data can be determined as described above; 9 bits for the Huffman codebook 5 and 8 bits for the Huffman codebook 6.
For the Huffman codebooks 3 and 4, the code length of Huffman-encoded data is calculated as follows. The Huffman codebooks 3 and 4 are so-called unsigned codebooks which are used for encoding data without a sign (unsigned data). When using an unsigned codebook, the absolute value of input data is Huffman-encoded, while the number of ignored signs are separately counted and added to the code amount of the Huffman encoding operation. The number of ignored signs corresponds to the number of non-zero elements (elements that require a sign) of the data to be encoded. The code length which would result when Huffman-encoding data with such an unsigned Huffman codebook can be obtained as follows.
First, an index value xe2x80x9cindex0xe2x80x9d is calculated from Expression (3) below:
index0=abs(D0)*(k{circumflex over ( )}3)+abs(D1)*(k{circumflex over ( )}2)+abs(D2)*k+abs(D3)xe2x80x83xe2x80x83(3)
where D0, D1, D2 and D3 respectively denote the four spectral data elements (values) of SFB2, xe2x80x9cabs(x)xe2x80x9d denotes an absolute value of x, xe2x80x9c0xe2x80x9d denotes an exponentiation, and k=LAV+1.
The calculated value of xe2x80x9cindex0xe2x80x9d is used as the index value for obtaining xe2x80x9clengthxe2x80x9d for each of Huffman codebooks 3 and 4. For SFB2 shown in FIG. 15, for example, D0=1, D1=xe2x88x921, D2=1, D3=0 and LAV=2. Thus, index0=39. Referring to the Huffman codebook 3 shown in FIG. 16, a length=6 is determined for index0=39. Since the sign information bits are not included in the codeword obtained from the Huffman codebook 3, sign information is needed to restore the code bits. The number of sign information bits needed is equal to the number of non-zero elements among the four elements in the spectral data of SFB2. SFB2 shown in FIG. 15 includes three non-zero elements. Therefore, three sign information bits need to be added to the Huffman-encoded codeword. As a result, the code length of the Huffman-encoded data is 9 (bits) (length=6+three sign information bits).
Referring to the Huffman codebook 4 as shown in FIG. 17, a length=4 can be determined for index0=39. Again, three sign information bits need to be added to length=4. Therefore, the code length of the Huffman-encoded data is 7 (bits) (length=4+three sign information bits).
Thus, the code lengths which would result when Huffman-encoding SFB2 with the Huffman codebooks 3, 4, 5 and 6 are 9, 7, 9 and 8, respectively. Therefore, the Huffman-encoded 4 is selected, with which the smallest code length is obtained.
Similarly, the optimal Huffman codebook is selected and used for Huffman-encoding each of the other SFBs. The Huffman encoding operation, which is simple by itself, is effected by outputting as encoded data a codeword (hexadecimal) for each index number (e.g., index0, index1, etc., which can be obtained as described above) from the selected Huffman codebooks.
Then, for each SFB, the codebook number of the selected Huffman codebook is encoded. This operation of encoding a Huffman codebook number is performed as follows according to the MPEG2-AAC standard. The codebook number of the Huffman codebook selected for the SFB of interest is encoded with four bits. Then, a value indicating whether the same Huffman codebook is selected for any other SFB which is contiguous with the SFB of interest is encoded with five bits. In the example shown in FIG. 15, the Huffman codebook 6 is selected for contiguous SFBs (SFB0 and SFB1). Therefore, for SFB0, the codebook number of the Huffman codebook 6 (i.e., xe2x80x9c6xe2x80x9d) is encoded with four bits (0110), and the value (xe2x80x9c1xe2x80x9d) (which indicates that the same Huffman codebook is also selected for the following SFB (SFB1)) is encoded with five bits (00001). Next, for SFB2, the Huffman codebook 4 is selected. Therefore, the codebook number of the Huffman codebook 4 (i.e., xe2x80x9c4xe2x80x9d) is encoded with four bits (0100). The following bit stream is dependent on the Huffman codebook selected for the following SFB (SFB3), and will not be discussed below. The codebook number of the selected Huffman codebook is similarly encoded for the subsequent SFBs.
A problem associated with the above-described conventional method is that the process of selecting the optimal Huffman codebook for each SFB takes a large amount of computation. This problem can be attributed in part to the calculation of the number of sign information bits, which is performed each time an unsigned codebook is selected. The problem can also be attributed to the operation of obtaining a code length which would result when encoding the SFB of interest with a Huffman codebook, which is performed separately for each of the candidate Huffman codebooks.
Another problem associated with the conventional method is that the method may not always select a Huffman codebook that is optimal for an SFB in view of the code amount needed to encode the codebook number of each selected Huffman codebook. In other words, the conventional method selects a Huffman codebook for each SFB so as to minimize the code amount of encoded data of that SFB. The conventional method cannot select the optimal Huffman codebook so as to minimize the total code amount of all encoded SFBs while taking into consideration the code amount needed to encode the codebook number of each selected Huffman codebook.
According to one aspect of this invention, there is provided an encoder including: a number G of storage sections (G is an integer equal to or greater than 1) for storing a number G of groups of data; a Huffman codebook selection section for selecting one of a number H of Huffman codebooks (H is an integer equal to or greater than 1) for each of the groups of data stored in the respective storage sections, each of the Huffman codebooks having a codebook number: a number G of Huffman encoding sections, each of the Huffman encoding sections Huffman-encoding a corresponding one of the G groups of data by using one of the Huffman codebooks which is selected by the Huffman codebook selection section for the one group of data: and a codebook number encoding section for encoding the codebook number of each Huffman codebook selected by the Huffman codebook selection section. The Huffman codebook selection section includes a code length calculation section for calculating a code length which would result from a Huffman encoding operation of each of the G groups of data using each Huffman codebook, and a control section for selecting one of the Huffman codebooks which is suitable for the group of data based on the code length calculated by the code length calculation section. When the Huffman codebook selected is an unsigned codebook, a number of bits required for sign information has previously been added to the code length calculated by the code length calculation section.
In one embodiment of the invention, the code length calculation section has a table of data including a code length previously calculated for each Huffman codebook.
According to another aspect of this invention, there is provided an encoder including: a number G of storage sections (G is an integer equal to or greater than 1) storing a number G of groups of data; a Huffman codebook selection section for selecting one of a number H of Huffman codebooks (H is an integer equal to or greater than 1) for each of the groups of data stored in the respective storage sections, each of the Huffman codebooks having a codebook number; a number G of Huffman encoding sections, each of the Huffman encoding sections Huffman-encoding a corresponding one of the G groups of data by using one of the Huffman codebooks which is selected by the Huffman codebook selection section for the one group of data; and a codebook number encoding section for encoding the codebook number of each Huffman codebook selected by the Huffman codebook selection section. The Huffman codebook selection section includes a code length calculation section for calculating a code length which would result from a Huffman encoding operation of each of the G groups of data using each Huffman codebook, and a control section for selecting one of the Huffman codebooks which is suitable for the group of data based on the code length calculated by the code length calculation section. The code length calculation section is capable of simultaneously obtaining code lengths for a plurality of Huffman codebooks.
In one embodiment of the invention, the code length calculation section is adapted to output respective code lengths which would result from Huffman encoding operations of the one group of data, for a plurality of Huffman codebooks. The control section selects one of the Huffman codebooks for which a smallest code length is output from the code length calculation section.
In one embodiment of the invention, the code length calculation section is adapted to output respective code lengths which would result from Huffman encoding operations of the one group of data, for a plurality of Huffman codebooks. The control section selects one of the Huffman codebooks based on the code length of the Huffman codebook output from the code length calculation section and in view of the codebook number of the Huffman codebook.
In one embodiment of the invention, the control section selects one of the Huffman codebooks for a (g+1)th group of data (g is an integer such that 1xe2x89xa6gxe2x89xa6Gxe2x88x921) by first obtaining a code length Bmin and another code length Bg, the code length Bmin being a code length which would result from a Huffman encoding operation of the (g+1)th group of data using a Huffman codebook Hmin for which a smallest code length is output from the code length calculation section, and the code length Bg being a code length which would result from a Huffman encoding operation of a gth group of data using a Huffman codebook Hg which has been selected for the gth group of data, and then selecting the Huffman codebook Hmin if Bmin less than (Bgxe2x88x92A) (A is a predetermined integer) or the Huffman codebook Hg if Bminxe2x89xa7(Bgxe2x88x92A).
In one embodiment of the invention, the control section selects one of the Huffman codebooks for which a smallest code length is output from the code length calculation section as a Huffman codebook for a first group of data.
In one embodiment of the invention, the control section selects one of the Huffman codebooks for a (gxe2x88x921)th group of data (g is an integer such that 2xe2x89xa6gxe2x89xa6G) by first obtaining a code length Bmin and another code length Bg, the code length Bmin being a code length which would result from a Huffman encoding operation of the (gxe2x88x921)th group of data using a Huffman codebook Hmin for which a smallest code length is output from the code length calculation section, and the code length Bg being a code length which would result from a Huffman encoding operation of a gth group of data using a Huffman codebook Hg which has been selected for the gth group of data, and then selecting the Huffman codebook Hmin if Bmin less than (Bgxe2x88x92A) (A is a predetermined integer) or the Huffman codebook Hg if Bminxe2x89xa7(Bgxe2x88x92A).
In one embodiment of the invention, the control section selects one of the Huffman codebooks for which a smallest code length is output from the code length calculation section as a Huffman codebook for a Gth group of data.
In one embodiment of the invention, when a same Huffman codebook is selected for two or more contiguous groups of data, the codebook number encoding section encodes the codebook number of the Huffman codebook and the number of the contiguous groups of data with a number of bits equal to the predetermined integer A.
In one embodiment of the invention, the H Huffman codebooks are eleven Huffman codebooks used for Huffman-encoding of spectral data as defined in the MPEG2-AAC standard.
In one embodiment of the invention, the code length calculation section is adapted to output respective code lengths which would result when encoding data using Huffman codebooks 1-4 defined in the MPEG2-AAC standard. The code length calculation section has a first table including respective code lengths which would result when encoding data by using Huffman codebooks 1 and 2 for a common index value and a second table including respective code lengths which would result when encoding data by using Huffman codebooks 3 and 4 for the common index value.
In one embodiment of the invention, a number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 3 and 4 which are included in the second table.
In one embodiment of the invention, the first table includes respective values of T1(F1(a, b, c, d)) and T2 (F1(a, b, c, d)) for i1, and the second table includes respective values of T3(F2(a, b, c, d))+nonz(a, b, c, d) and T4(F2(a, b, c, d))+nonz(a, b, c, d) for i2, where: nonz(w, x, y, z) is a function which gives the number of non-zero values among w, x, y and z; F1(w, x, y, z) is a function defined as follows: F1(w, x, y, z)=27*(w+1)+9*(x+1)+3*(y+1) +(z+1) (where an absolute value of each of w, x, y and z is 1 or less): F2(w, x, y, z) is a function defined as follows: F2(w, x, y, z)=27*abs(w)+9*abs(x)+3*abs(y)+abs(z) (where an absolute value of each of w, x, y and z is 2 or less); abs(x) is a function which gives an absolute value of x; T1(index) to T4(index) are each a function which gives a code length which would result when encoding data by using Huffman codebooks 1 to 4, respectively; a, b, c and d are integers representing a group of data; and i1 and i2 are index values calculated as a function of the integers a, b, c and d.
In one embodiment of the invention, i1=(X{circumflex over ( )}3)*(a+1) +(X{circumflex over ( )}2)*(b+1)+X*(c+1)+(d+1), where: X is a positive number equal to or greater than 3; i2=(Y{circumflex over ( )}3)*abs(a)+(Y{circumflex over ( )}2)*abs(b) +Y*abs(c)+abs(d), where: Y is a positive number equal to or greater than 3; and the symbol xe2x80x9c{circumflex over ( )}xe2x80x9d denotes an exponentiation.
In one embodiment of the invention, the index value i1 is obtained through a bit connecting operation of a, b, c and d each of which is represented with X bits or more, where X is a positive number equal to or greater than 2. The index value i2 is obtained through a bit connecting operation of abs(a), abs(b), abs(c) and abs(d) each of which is represented with Y bits or more, where Y is a positive number equal to or greater than 2.
In one embodiment of the invention, the code length calculation section is adapted to output respective code lengths which would result when encoding data using Huffman codebooks 1-4 defined in the MPEG2-AAC standard. The code length calculation section has a table of data including respective code lengths which would result when encoding data by using Huffman codebooks 1 to 4 for a common index value.
In one embodiment of the invention, a number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 3 and 4 which are included in the table.
In one embodiment of the invention, the table includes respective values of T1(F1(a, b, c, d)), T2(F1(a, b, c, d)), T3(F2(a, b, c, d))+nonz(a, b, c, d) and T4(F2(a, b, c, d))+nonz(a, b, c, d) for j, where: nonz(w, x, y, z) is a function which gives the number of non-zero values among w, x, y and z; F1(w, x, y, z) is a function defined as follows: F1(w, x, y, z)=27*(w+1)+9*(x+1)+3*(y+1) +(z+1) (where an absolute value of each of w, x, y and z is 1 or less); F2(w, x, y, z) is a function defined as follows: F2(w, x, y, z)=27*abs(w)+9*abs(x)+3*abs(y)+abs(z) (where an absolute value of each of w, x, y and z is 2 or less); abs(x) is a function which gives an absolute value of x; T1(index) to T4(index) are each a function which gives a code length which would result when encoding data by using Huffman codebooks 1 to 4, respectively; a, b, c and d are integers representing a group of data; and j is an index value calculated as a function of the integers a, b, c and d.
In one embodiment of the invention, the index value j is obtained through a bit connecting operation of a, b, c and d each of which is represented with Y bits or more, where Y is a positive number equal to or greater than 2.
In one embodiment of the invention, the code length calculation section is adapted to output respective code lengths which would result when encoding data using Huffman codebooks 5-10 defined in the MPEG2-AAC standard. The code length calculation section has a first table including respective code lengths which would result when encoding data by using Huffman codebooks 5 and 6 for a common index value, a second table including respective code lengths which would result when encoding data by using Huffman codebooks 7 and 8 for a common index value, and a third table including respective code lengths which would result when encoding data by using Huffman codebooks 9 and 10 for a common index value.
In one embodiment of the invention, a number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 7 and 8 which are included in the second table. A number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 9 and 10 which are included in the third table.
In one embodiment of the invention, the first table includes respective values of T5(F3(a, b)) and T6(F3(a, b)) for i3, the second table includes respective values of T7(F4(a, b))+nonz(a, b) and T8(F4(a, b))+nonz(a, b) for i4, and the third table includes respective values of T9(F5(a, b))+nonz(a, b) and T10(F5(a, b))+nonz(a, b) for i5, where nonz(x, y) is a function which gives the number of non-zero values among x and y; F3(x, y) is a function defined as follows: F3(x, y)=9*(x+4)+(y+4) (where an absolute value of each of x and y is 4 or less); F4(x, y) is a function defined as follows: F4(x, y)=8*abs(x)+abs(y) (where an absolute value of each of x and y is 7 or less); F5(x, y) is a function defined as follows: F5(x, y)=13*abs(x)+abs(y) (where an absolute value of each of x and y is 12 or less); abs(x) is a function which gives an absolute value of x; T5(index) to T10(index) are each a function which gives a code length which would result when encoding data by using Huffman codebooks 5 to 10 defined in the MPEG2-AAC standard, respectively; a and b are integers representing a group of data; and i3, i4 and i5 are index values calculated as a function of the integers a and b.
In one embodiment of the invention, i3=X*(a+4)+(b+4), where X is a positive number equal to or greater than 9; i4=Y*abs(a)+abs(b), where Y is a positive number equal to or greater than 8: and i5=Z*abs(a)+abs(b), where Z is a positive number equal to or greater than 13.
In one embodiment of the invention, the index value i3 is obtained through a bit connecting operation of a and b each of which is represented with X bits or more, where X is a positive number equal to or greater than 4. The index value i4 is obtained through a bit connecting operation of a and b each of which is represented with Y bits or more, where Y is a positive number equal to or greater than 4. The index value i5 is obtained through a bit connecting operation of a and b each of which is represented with Z bits or more, where Z is a positive number equal to or greater than 5.
In one embodiment of the invention, the code length calculation section is adapted to output respective code lengths which would result when encoding data using Huffman codebooks 5-10 defined in the MPEG2-AAC standard. The code length calculation section has a table including respective code lengths which would result when encoding data by using Huffman codebooks 5 to 10 for a common index value.
In one embodiment of the invention, a number of bits required for sign information has previously been added to each of the code lengths for Huffman codebooks 7 to 10 which are included in the table.
In one embodiment of the invention, the table includes respective values of T5(F3(a, b)), T6(F3(a, b)), T7(F4(a, b))+nonz(a, b),T8(F4(a, b))+nonz(a, b),T9(F5(a, b))+nonz(a, b) and T10(F5(a, b))+nonz(a, b) fork, where: nonz(x, y) is a function which gives the number of non-zero values among x and y; F3(x, y) is a function defined as follows: F3(x, y)=9*(x+4)+(y+4) (where an absolute value of each of x and y is 4 or less); F4(x, y) is a function defined as follows: F4(x, y)=8*abs(x)+abs(y) (where an absolute value of each of x and y is 7 or less); F5(x, y) is a function defined as follows: F5(x, y)=13*abs(x)+abs(y) (where an absolute value of each of x and y is 12 or less); abs(x) is a function which gives an absolute value of x; T5(index) to T10(index) are each a function which gives a code length which would result when encoding data by using Huffman codebooks 5 to 10 defined in the MPEG2-AAC standard, respectively; a and b are integers representing a group of data: and k is an index value calculated as a function of the integers a and b.
In one embodiment of the invention, the index value k is obtained through a bit connecting operation of a and b each of which is represented with Z bits or more, where Z is a positive number equal to or greater than 5.
In one embodiment of the invention, the code length calculation section is adapted to output an invalid signal which indicates that a Huffman codebook is invalid when an input data value is outside a variable range within which a code length can be calculated using the Huffman codebook. The control section is adapted not to select a Huffman codebook when the control section receives an invalid signal for the Huffman codebook.
In one embodiment of the invention, the value of the function T1(F1(a, b, c, d)) and the value of the function T2(F1(a, b, c, d)) are stored respectively on a MSB side and on a LSB side with respect to the index value i1, with at least m1 bits of xe2x80x9c0xe2x80x9d (m1 is a positive integer) being inserted between the value of the function T1 and the value of the function T2. The value of the function T3(F2(a, b, c, d))+nonz(a, b, c, d) and the value of the function T4(F2(a, b, c, d))+nonz(a, b, c, d) are stored respectively on a MSB side and on a LSB side with respect to the index value i2, with at least m1 bits of xe2x80x9c0xe2x80x9d being inserted between the value of the function T3 and the value of the function T4.
In one embodiment of the invention, the value of the function T1(F1(a, b, c, d)), the value of the function T2(F1(a, b, c, d)), the value of the function T3(F2(a, b, c, d))+nonz(a, b, c, d) and the value of the function T4(F2(a, b, c, d))+nonz(a, b, c, d) are stored in this order from a MSB side to a LSB side with respect to the index value j, with at least m1 bits of xe2x80x9c0xe2x80x9d (m1 is a positive integer) being inserted between the value of T1 and the value of T2, between the value of T2 and the value of T3, and between the value of T3 and the value of T4.
In one embodiment of the invention, the value of m1 is an integer value obtained by rounding up a value of the logarithm of 2 to the base of n1 (log2(n1)), where n1 is a value obtained by dividing a maximum number of data included in each group among the G groups of data by 4.
In one embodiment of the invention, the value of the function T5(F3(a, b)) and the value of the function T6(F3(a, b)) are stored respectively on a MSB side and on a LSB side with respect to the index value i3, with at least m2 bits of xe2x80x9c0xe2x80x9d (m2 is a positive integer) being inserted between the value of the function T5 and the value of the function T6. The value of the function T7(F4(a, b))+nonz(a, b) and the value of the function T8(F4(a, b))+nonz(a, b) are stored respectively on a MSB side and on a LSB side with respect to the index value i4, with at least m2 bits of xe2x80x9c0xe2x80x9d being inserted between the value of the function T7 and the value of the function T8. The value of the function T9(F5(a, b))+nonz(a, b) and the value of the function T10(F5(a, b))+nonz(a, b) are stored respectively on a MSB side and on a LSB side with respect to the index value is, with at least m2 bits of xe2x80x9c0xe2x80x9d being inserted between the value of the function T9 and the value of the function T10.
In one embodiment of the invention, the value of the function T5(F3(a, b)), the value of the function T6(F3(a, b)), the value of the function T7(F4(a, b))+nonz(a, b), the value of the function T8(F4(a, b))+nonz(a, b), the value of the function T9(F5(a, b))+nonz(a, b) and the value of the function T10(F5(a, b))+nonz(a, b) are stored in this order from a MSB side to a LSB side with respect to the index value k, with at least m2 bits of xe2x80x9c0xe2x80x9d (m2 is a positive integer) being inserted between the value of T5 and the value of T6, between the value of T6 and the value of T7, between the value of T7 and the value of T8, between the value of T8 and the value of T9, and between the value of T9 and the value of T10.
In one embodiment of the invention, the value of m2 is an integer value obtained by rounding up a value of the logarithm of 2 to the base of n2 (log2(n2)), where n2 is a value obtained by dividing a maximum number of data included in each group among the G groups of data by 2.
Thus, the invention described herein makes possible the advantages of providing an encoder capable of selecting the optimal Huffman codebook from among a plurality of Huffman codebooks so as to encode digital data by using the optimally selected Huffman codebook. The encoder is also capable of selecting the optimal Huffman codebook within a reduced amount of time and efficiently encoding the digital data with a small amount of calculation.
This and other advantages of the present invention will become apparent to those skilled in the art upon reading and understanding the following detailed description with reference to the accompanying figures.